import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

import static jdk.internal.vm.PostVMInitHook.run;

class small implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
}

class downSort implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}
public class topk {

    public static void main(String[] args) {
        Random random = new Random();
//        int[] array = new int[100];
        int[] array = {1,3,5,7,2,4,6,8};
//        for (int i = 0; i < 100; i++) {
//            array[i] = random.nextInt(0,200);
//        }
        int k = 4;
        System.out.println(Arrays.toString(array));
        int[] tmp = Arrays.copyOf(run(array, k),k);
        System.out.println(Arrays.toString(tmp));

    }

    private static int[] run(int[] array,int k) {
        if (k > array.length) {
            k = array.length;
        } else if (k == 0) {
            int[] tmp = new int[0];
            return tmp;
        }
        downSort d = new downSort();
        small s = new small();
        PriorityQueue<Integer> heap = new PriorityQueue<>(d);//小堆

        for (int i = 0; i < k; i++) {
            heap.offer(array[i]);
        }

        //遍历剩下的元苏
        for (int i = k; i < array.length; i++) {
            if (array[i] < heap.peek()) {
                heap.poll();
                heap.offer(array[i]);
            }
        }
        Integer[] tmp = new Integer[k];
        heap.toArray(tmp);
        Arrays.sort(tmp, d);
        //拆箱
        int[] end = new int[k];
        for (int i = 0; i < tmp.length; i++) {
            end[i] = tmp[i].intValue();
        }
        return end;
    }
}
